<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="PvC7e" id="PvC7e"><span data-lake-id="u2f2d3d8f" id="u2f2d3d8f">典型回答</span></h1>
  <p data-lake-id="u17ad9ac1" id="u17ad9ac1"><span data-lake-id="u20f091a7" id="u20f091a7">从定义上讲：</span></p>
  <p data-lake-id="uc8ddb4c6" id="uc8ddb4c6"><span data-lake-id="uf28dc763" id="uf28dc763">数组和链表都是数据的集合。</span></p>
  <ol list="u6f06a693">
   <li fid="uc4299a80" data-lake-id="uf8a02083" id="uf8a02083"><strong><span data-lake-id="u9bfb74d8" id="u9bfb74d8">数组中每个元素都是连续的</span></strong><span data-lake-id="u1cd0fd49" id="u1cd0fd49">，</span><strong><span data-lake-id="u2c9047ab" id="u2c9047ab">通过下标进行访问</span></strong><span data-lake-id="u5fad3904" id="u5fad3904">，当我们获取到下标后，就可以随意访问数组中的值</span></li>
  </ol>
  <p data-lake-id="ud832110b" id="ud832110b"><br></p>
  <ol list="u6f06a693" start="2">
   <li fid="uc4299a80" data-lake-id="u30c968f2" id="u30c968f2"><strong><span data-lake-id="u8f0adaa4" id="u8f0adaa4">链表中的元素则是不连续的</span></strong><span data-lake-id="uf53d72cb" id="uf53d72cb">，必须获得链表中某个元素后，才能顺序访问该元素的周围元素，我们没办法随意访问链表中的元素。链表分为单向链表，双向链表，环形链表等</span></li>
  </ol>
  <p data-lake-id="ua9068148" id="ua9068148"><br></p>
  <p data-lake-id="uc5bdbb4b" id="uc5bdbb4b"><span data-lake-id="u053ed635" id="u053ed635">从实现上来讲：</span></p>
  <ol list="uc594bd8f">
   <li fid="u3371a6f7" data-lake-id="uacbc0a0a" id="uacbc0a0a"><strong><span data-lake-id="u9fe5b256" id="u9fe5b256">数组可以由一块连续区域的内存实现</span></strong><span data-lake-id="u1110b1c6" id="u1110b1c6">，其中，内存地址可以作为数组的下标，该地址中的值就是数组中元素的值。因为数组占用的是一块空间，所以数组的大小申请之后就会固定；</span></li>
  </ol>
  <p data-lake-id="u019c71e3" id="u019c71e3"><br></p>
  <ol list="uc594bd8f" start="2">
   <li fid="u3371a6f7" data-lake-id="u878b24f8" id="u878b24f8"><strong><span data-lake-id="uae2ed7da" id="uae2ed7da">链表可以由不连续的内存存储实现</span></strong><span data-lake-id="ue0e33086" id="ue0e33086">，每个元素都会存储下一个元素的地址。（如果是双向链表的话，元素则会还会存储上个元素的地址）。因为链表中存储了元素的地址，所以链表可以在内存足够的情况下随意申请空间</span></li>
  </ol>
  <p data-lake-id="u59834b82" id="u59834b82"><br></p>
  <p data-lake-id="uea54121d" id="uea54121d"><span data-lake-id="uacd500b5" id="uacd500b5">如下图所示：</span></p>
  <p data-lake-id="uf50e4c24" id="uf50e4c24"><span data-lake-id="u49ce4e10" id="u49ce4e10">​</span><br></p>
  <p data-lake-id="u9816ded7" id="u9816ded7"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676649140452-bc03a9a1-b355-4513-be6a-a8b23cb28bc0.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_14%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u852e452d" id="u852e452d"><br></p>
  <p data-lake-id="u95d86a68" id="u95d86a68"><span data-lake-id="u9afad646" id="u9afad646">数组和链表的区别如下所示：</span></p>
  <table data-lake-id="Nbwf0" id="Nbwf0" margin="true" width-mode="contain" class="lake-table" style="width: 699px">
   <colgroup>
    <col width="148">
    <col width="301">
    <col width="250">
   </colgroup>
   <tbody>
    <tr data-lake-id="u921a8bad" id="u921a8bad">
     <td data-lake-id="u4f9929ce" id="u4f9929ce">
      <p data-lake-id="ua1617332" id="ua1617332"><span data-lake-id="u477121c4" id="u477121c4">比较项</span></p></td>
     <td data-lake-id="u4f82b339" id="u4f82b339">
      <p data-lake-id="u48529df5" id="u48529df5"><span data-lake-id="u977dc0c8" id="u977dc0c8">数组</span></p></td>
     <td data-lake-id="u0b45c7e2" id="u0b45c7e2">
      <p data-lake-id="ufa20d6dd" id="ufa20d6dd"><span data-lake-id="ue42f9568" id="ue42f9568">链表</span></p></td>
    </tr>
    <tr data-lake-id="u7b21ae1b" id="u7b21ae1b">
     <td data-lake-id="u8f97a01d" id="u8f97a01d">
      <p data-lake-id="ub568e2b3" id="ub568e2b3"><span data-lake-id="u77fb6cce" id="u77fb6cce">内存中是否连续</span></p></td>
     <td data-lake-id="ucf341d72" id="ucf341d72">
      <p data-lake-id="ud13aa4e9" id="ud13aa4e9"><span data-lake-id="u2bfb16b0" id="u2bfb16b0">是</span></p></td>
     <td data-lake-id="udba641d4" id="udba641d4">
      <p data-lake-id="u97ba6cdd" id="u97ba6cdd"><span data-lake-id="uf2a898b4" id="uf2a898b4">否</span></p></td>
    </tr>
    <tr data-lake-id="ub1da7f54" id="ub1da7f54">
     <td data-lake-id="ue4742921" id="ue4742921">
      <p data-lake-id="uab36270f" id="uab36270f"><span data-lake-id="ubf98e1d9" id="ubf98e1d9">查询效率</span></p></td>
     <td data-lake-id="u7f972a79" id="u7f972a79">
      <ol list="u03fd1d5a">
       <li fid="u2e67d79e" data-lake-id="u525c541c" id="u525c541c"><span data-lake-id="ube32c997" id="ube32c997">通过下标查是O(1)</span></li>
       <li fid="u2e67d79e" data-lake-id="u3043eab4" id="u3043eab4"><span data-lake-id="u586960cf" id="u586960cf">通过数值查是O(n)，如果是有序数组则O(logn)</span></li>
      </ol></td>
     <td data-lake-id="u27a0ba0e" id="u27a0ba0e">
      <p data-lake-id="u3a3b53d4" id="u3a3b53d4"><span data-lake-id="u43cb0f83" id="u43cb0f83">O(n)</span></p></td>
    </tr>
    <tr data-lake-id="ucc3457a8" id="ucc3457a8">
     <td data-lake-id="u91290da8" id="u91290da8">
      <p data-lake-id="u363caa36" id="u363caa36"><span data-lake-id="u5177596d" id="u5177596d">占用空间</span></p></td>
     <td data-lake-id="ub0bf3530" id="ub0bf3530">
      <ol list="u9710c3c3">
       <li fid="u544d9003" data-lake-id="ucc917365" id="ucc917365"><span data-lake-id="u59a87728" id="u59a87728">直接申请空间，当元素个数不确定时，容易浪费</span></li>
      </ol></td>
     <td data-lake-id="udf18f8aa" id="udf18f8aa">
      <ol list="u64fda5bf">
       <li fid="u06a1b7d0" data-lake-id="u4f18565b" id="u4f18565b"><span data-lake-id="ua00a2096" id="ua00a2096">相对数组来说会存储前后指针</span></li>
       <li fid="u06a1b7d0" data-lake-id="u71b0876f" id="u71b0876f"><span data-lake-id="u4e98be07" id="u4e98be07">大小和元素个数相同</span></li>
      </ol></td>
    </tr>
    <tr data-lake-id="ua982d7a0" id="ua982d7a0">
     <td data-lake-id="u546100af" id="u546100af">
      <p data-lake-id="u63415304" id="u63415304"><span data-lake-id="ucfc43d05" id="ucfc43d05">插入/删除</span></p></td>
     <td data-lake-id="ua72f77d0" id="ua72f77d0">
      <p data-lake-id="u737a36c4" id="u737a36c4"><span data-lake-id="ud36eca54" id="ud36eca54">数组需要移动n/2个元素</span></p></td>
     <td data-lake-id="u909d12cb" id="u909d12cb">
      <p data-lake-id="u17722559" id="u17722559"><span data-lake-id="ua6e92050" id="ua6e92050">链表只需要修改指针</span></p></td>
    </tr>
   </tbody>
  </table>
  <h1 data-lake-id="tNkqp" id="tNkqp"><span data-lake-id="u7652828a" id="u7652828a">知识扩展</span></h1>
  <h2 data-lake-id="lEGuP" id="lEGuP"><span data-lake-id="ufcb2b980" id="ufcb2b980">什么是双向链表和环形链表</span></h2>
  <ol list="uf183d7f2">
   <li fid="u0ac2cabd" data-lake-id="uc51c8a89" id="uc51c8a89"><span data-lake-id="u89d9c2a0" id="u89d9c2a0">双向链表是指每个元素不仅指向下一个元素，还会指向上一个元素，如下图所示：</span></li>
  </ol>
  <p data-lake-id="ua9e8323a" id="ua9e8323a"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676650457044-91b000e7-9208-4329-96d7-64e044062db0.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_16%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u7f2b7a3f" id="u7f2b7a3f"><br></p>
  <ol list="ueb575f81" start="2">
   <li fid="u33776e29" data-lake-id="u0388b42b" id="u0388b42b"><span data-lake-id="u50407485" id="u50407485">环形链表指链表的最后一个元素会指向链表的第一个元素；或者链表的最后一个元素会指向链表中间的某个元素，如下图所示：</span></li>
  </ol>
  <p data-lake-id="uc45cb5dd" id="uc45cb5dd"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676650610006-0fe053f0-bc0f-4e5c-819c-219081f6ed0d.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_21%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <h2 data-lake-id="XKfc7" id="XKfc7"><span data-lake-id="u2a591b71" id="u2a591b71">相关算法</span></h2>
  <ol list="u35c59217">
   <li fid="u96d053c0" data-lake-id="u645e0fff" id="u645e0fff"><span data-lake-id="u343628cf" id="u343628cf">反转链表：</span><a href="https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/" target="_blank" data-lake-id="u262e2edf" id="u262e2edf"><span data-lake-id="u6162e1b7" id="u6162e1b7">https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/</span></a></li>
   <li fid="u96d053c0" data-lake-id="u515b2c8e" id="u515b2c8e"><span data-lake-id="ua1b5e377" id="ua1b5e377">合并两个有序数组：</span><a href="https://leetcode.cn/problems/merge-sorted-array/" target="_blank" data-lake-id="uecf0fe83" id="uecf0fe83"><span data-lake-id="u3c33f15d" id="u3c33f15d">https://leetcode.cn/problems/merge-sorted-array/</span></a></li>
   <li fid="u96d053c0" data-lake-id="u5abe2333" id="u5abe2333"><span data-lake-id="u80949aa9" id="u80949aa9">判断环形链表：</span><a href="https://leetcode.cn/problems/linked-list-cycle/" target="_blank" data-lake-id="u2b5b3bcb" id="u2b5b3bcb"><span data-lake-id="u52775874" id="u52775874">https://leetcode.cn/problems/linked-list-cycle/</span></a></li>
  </ol>
 </body>
</html>